// class Solution {
//     public int ladderLength(String beginWord, String endWord, List<String> wordList) {
//         Map<String, Boolean> visited = new HashMap<>(); // 记录已经访问过的序列
        
//         // 判断特殊情况
//         if (beginWord.equals(endWord)) {
//             return 0;
//         }
//         if (!wordList.contains(endWord)) {
//             return 0;
//         }

//         Queue<String> queue = new LinkedList<>();
//         queue.offer(beginWord);
//         visited.put(beginWord, true);
//         int ret = 1; // 这里求的是单词数目，第一层也有一个单词
//         while (!queue.isEmpty()) {
//             ret++;
//             int size = queue.size(); // 求出当前层的个数
//             while (size-- != 0) {
//                 String s = queue.poll();
//                 int n = s.length(); // 这里并未说明字符串的长度固定为多少
//                 for (int i = 0; i < n; i++) {
//                     char[] tmp = s.toCharArray();
//                     for (char j = 'a'; j <= 'z'; j++) { // 24个字母都试一下
//                         if (tmp[i] == j) { // 相同就不需要走下去了
//                             continue;
//                         }
//                         tmp[i] = j; // 将第i位的字符改为另外的字符
//                         String next = new String(tmp);
//                         // 判断是否符合要求（变化后的结果在字典中、未被访问过）
//                         if (wordList.contains(next) && !visited.containsKey(next)) {
//                             if (endWord.equals(next)) {
//                                 return ret;
//                             }
//                             queue.offer(next);
//                             visited.put(next, true);
//                         }
//                     }
//                 }
//             }
//         }
//         return 0;
//     }
// }


import java.util.*;

// 上面是超时版本，使用哈希表减少查询时间
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Map<String, Boolean> visited = new HashMap<>(); // 记录已经访问过的序列
        Map<String, Boolean> hash = new HashMap<>();
        for (String s : wordList) {
            hash.put(s, true);
        }
        
        // 判断特殊情况
        if (beginWord.equals(endWord)) {
            return 0;
        }
        if (!hash.containsKey(endWord)) {
            return 0;
        }

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visited.put(beginWord, true);
        int ret = 1; // 这里求的是单词数目，第一层也有一个单词
        while (!queue.isEmpty()) {
            ret++;
            int size = queue.size(); // 求出当前层的个数
            while (size-- != 0) {
                String s = queue.poll();
                int n = s.length(); // 这里并未说明字符串的长度固定为多少
                for (int i = 0; i < n; i++) {
                    char[] tmp = s.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) { // 24个字母都试一下
                        if (tmp[i] == j) { // 相同就不需要走下去了
                            continue;
                        }
                        tmp[i] = j; // 将第i位的字符改为另外的字符
                        String next = new String(tmp);
                        // 判断是否符合要求（变化后的结果在字典中、未被访问过）
                        if (hash.containsKey(next) && !visited.containsKey(next)) {
                            if (endWord.equals(next)) {
                                return ret;
                            }
                            queue.offer(next);
                            visited.put(next, true);
                        }
                    }
                }
            }
        }
        return 0;
    }
}